Матч 236, Бизнес задания (BusinessTasks)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Список list содержит набор заданий, которые должен выполнить бизнесмен. Для того, чтобы решить какое задание выполнять первым, он совершает следующую процедуру. Все задания располагаются в циклическом списке, то есть после последнего задания идет первый. Бизнесмен выбирает некоторое натуральное число n. Начиная с первого элемента, он считает по часовой стрелке до тех пор, пока не дойдет до n - ого задания, которое удаляет из списка. Затем счет продолжается по часовой стрелке, начиная со следующего после удаленного элемента. Процесс счета и удаления продолжается до тех пор, пока в списке не останется одно задание. Оно и выполняется первым.

По заданному списку заданий list и числу n следует найти задание, которое будет выполняться первым.

Класс: BusinessTasks

Метод: string getTask(vector<string> list, int n)

Ограничения: list содержит от 2 до 50 элементов, list[i] содержит от 1 до 50 символов ‘a’ – ‘z’, 1 £ n £ 10000000.

Вход. Массив list, содержащий набор заданий и число n.

Выход. Первое задание, которое будет выполнять бизнесмен согласно описанной в условии процедуре выбора.

Пример входа

list	n
{"a","b","c","d"}	2
{"a","b","c","d","e"}	3
{"alpha","beta","gamma","delta","epsilon"}	1

Пример выхода

"a"

"d"

"epsilon"

РЕШЕНИЕ

обработка массива + моделирование

Задачу будем решать, моделируя описанный процесс подсчета и удаления заданий. С учетом того, что значение n может быть велико, следует воспользоваться правилом:

Если имеется k заданий, пронумерованных от 0 до k – 1, счет продолжается до n, а отсчет начинается с i - ого задания, то следующее удаляемое задание имеет номер (i + n) % k.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

class BusinessTasks

{

public:

string getTask(vector<string> list, int n)

{

int i, j, size = list.size();

n--;

for(j = i = 0; i < size - 1; i++)

{

j = (j + n) % list.size();

list.erase(list.begin() + j);

}

return list[0];

}

};